package com.learn.algorithm.dynamic.programming;

import java.util.Arrays;

public class LeetCode91 {

    public static int numDecodings(String str) {
        int n = str.length();
        int next = 1;
        int nextNext = 0;
        char[] s = str.toCharArray();
        for (int i = n - 1, cur; i >= 0; i--) {
            if (s[i] == '0') {
                cur = 0;
            } else {
                cur = next;
                // (i, i+1) 组合考虑
                if (i + 1 < n && (s[i] - '0') * 10 + (s[i + 1] - '0') <= 26) {
                    cur += nextNext;
                }
            }
            nextNext = next;
            next = cur;
        }

        return next;
    }

    public static int numDecodings3(String str) {
        int n = str.length();
        int[] dp = new int[n + 1];
        dp[n] = 1;
        char[] s = str.toCharArray();
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == '0') {
                dp[i] = 0;
            } else {
                dp[i] = dp[i + 1];
                // (i, i+1) 组合考虑
                if (i + 1 < n && (s[i] - '0') * 10 + (s[i + 1] - '0') <= 26) {
                    dp[i] += dp[i + 2];
                }
            }
        }

        return dp[0];
    }

    public static int numDecodings2(String s) {
        int[] dp = new int[s.length() + 1];
        Arrays.fill(dp, -1);
        return f2(s.toCharArray(), 0, dp);
    }

    // 记忆化搜索
    public static int f2(char[] str, int i, int[] dp) {
        if (i == str.length) {
            return 1;
        }
        if (dp[i] != -1) {
            return dp[i];
        }
        int ans;
        if (str[i] == '0') {
            return 0;
        } else {
            // i 位置是 0-9
            ans = f2(str, i + 1, dp);
            // (i, i+1) 组合考虑
            if (i + 1 < str.length && (str[i] - '0') * 10 + (str[i + 1] - '0') <= 26) {
                ans += f2(str, i + 2, dp);
            }
        }
        dp[i] = ans;
        return ans;
    }

    public static int numDecodings1(String s) {
        int[] dp = new int[s.length() + 1];
        Arrays.fill(dp, -1);
        return f2(s.toCharArray(), 0, dp);
    }

    // 暴力递归
    public static int f1(char[] str, int i) {
        if (i == str.length) {
            return 1;
        }
        int ans;
        if (str[i] == '0') {
            return 0;
        } else {
            // i 位置是 0-9
            ans = f1(str, i + 1);
            // (i, i+1) 组合考虑
            if (i + 1 < str.length && (str[i] - '0') * 10 + (str[i + 1] - '0') <= 26) {
                ans += f1(str, i + 2);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(numDecodings("12"));
        System.out.println(numDecodings("226"));
        System.out.println(numDecodings("06"));
    }
}
